D. Distinct array positions for keys based on priority
Solution: Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.
Q: When is it appropriate to use direct addressing?
A. When the array is comparatively large
B. When the universe U of keys is reasonably small
C. When the universe U of keys is reasonably large
D. When the array is comparatively small
Solution: Since each key is associated with a slot in the array, it is better to use direct addressing when the universe of keys is small as the array size grows with the increase in number of keys.
Q: What is the search complexity in direct addressing?
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(1)
Solution: Since every key has a unique array position, searching takes a constant time.
Q: What is the time complexity to insert an element into the direct address table?
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(1)
Solution: As every key has a unique array position, it takes constant time to insert an element.
Q: What is the advantage of using a dynamic set in direct addressing?
A. It saves time
B. It saves space
C. It saves both time and space
D. It reduces code complexity
Solution: Using a dynamic set, the size of the array is restricted to the number of keys, hence saves space. The complexity to implement dynamic array is larger than in normal case.
Q: What is the time complexity to delete an element from the direct address table?
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(1)
Solution: As every key has a unique array position, it takes constant time to delete an element, although the deleted position must be specified by nil.
Q: How is a bit vector better compared to a normal array for implementing the hash table?
A. It saves time
B. It saves space
C. It saves both time and space
D. It reduces code complexity
Solution: A bit vector is an array of bits of only 0s and 1s, a bit vector of length m takes much less space than an array of m pointers. The complexity to implement bit vector is larger than in normal case.
Q: What is the expected error by the estimator Chernoff bound on the samples performed without replacement?
A. O (log k!)
B. O (k!)
C. O (k2)
D. O (1/k½)
Solution: The expected error for estimating the Jaccard index using MinHash scheme for k different hash functions is O (1/k½). The expected error by the estimator Chernoff bound on the samples performed without replacement is O (1/k½).
Q: What is the time required for single variant hashing to maintain the minimum hash queue?
A. O (log n!)
B. O (n!)
C. O (n2)
D. O (n)
Solution: The expected error for estimating the Jaccard index using MinHash scheme for k different hash functions is O (1/k½). The time required for single variant hashing to maintain the minimum hash queue is O (n).
Q: How many bits are needed to specify the single permutation by min-wise independent family?
A. O (log n!)
B. O (n!)
C. Ω (n2)
D. Ω (n)
Solution: The time required for single variant hashing to maintain the minimum hash queue is O (n). Ω (n) bits are needed to specify the single permutation by min-wise independent family.